package demo.DataStrucAndAlgo.AlgorithmOfTen;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/1-08-01-20:21
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen     经典分治算法：汉诺塔
 */
/*
汉诺塔：
    三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
    并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
 */
public class DAC_divide_Conquer {
    public static void main(String[] args) {
        hanoiTower(3,'A','B','C');
    }

    /**
     * 分治算法解决汉诺塔问题
     * @param num   汉诺塔盘数
     * @param a     每次递归的起始位置
     * @param b     每次递归的暂留位置
     * @param c     每次递归的目标位置
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        if(num == 1){
            System.out.println("第1个盘从" + a + "移动到" + c);
        }else{
            //两个及以上的移动策略
            //最底层上面所有盘为一个整体，从起始位置移动到暂留位置
            hanoiTower(num-1,a,c,b);
            System.out.println("第" + num + "个盘从" + a + "移动到" + c);
            //将上面所有盘的整体，由暂留位置移动到目标位置
            hanoiTower(num-1,b,a,c);
        }
    }
}
